package gold.contest;

import gold.utils.InputUtil;
import org.junit.Test;

import java.util.ArrayList;
import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC6032 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
            List<long[]>[] graph = new List[n];
            List<long[]>[] reverseGraph = new List[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
                reverseGraph[i] = new ArrayList<>();
            }
            for (int[] edge : edges) {
                int from = edge[0];
                int to = edge[1];
                int weight = edge[2];
                graph[from].add(new long[]{to, weight});
                reverseGraph[to].add(new long[]{from, weight});
            }

            Long[] distFromSrc1 = dijkstra(graph, src1);
            Long[] distFromSrc2 = dijkstra(graph, src2);
            Long[] distFromDest = dijkstra(reverseGraph, dest);

            long res = Long.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (distFromSrc1[i] != null && distFromSrc2[i] != null && distFromDest[i] != null) {
                    res = Math.min(res, distFromSrc1[i] + distFromSrc2[i] + distFromDest[i]);
                }
            }
            return res < Long.MAX_VALUE ? res : -1;
        }

        private Long[] dijkstra(List<long[]>[] graph, int from) {
            Long[] dist = new Long[graph.length];

            PriorityQueue<Long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
            pq.offer(new Long[]{(long) from, 0L});
            while (!pq.isEmpty()) {
                Long[] cur = pq.poll();
                int to = cur[0].intValue();
                long weight = cur[1];
                if (dist[to] == null) {
                    dist[to] = weight;
                    for (long[] edge : graph[to]) {
                        pq.offer(new Long[]{edge[0], edge[1] + weight});
                    }
                }
            }
            return dist;
        }
    }

    class Solution_Time_Exceed {
        long MAX = Long.MAX_VALUE / 2;

        public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
            List<int[]>[] prevNode = new List[n];
            List<int[]>[] nextNode = new List[n];
            edges = shortenEdge(edges);

            for (int[] edge : edges) {
                if (null == prevNode[edge[1]]) prevNode[edge[1]] = new ArrayList<>();
                if (null == nextNode[edge[0]]) nextNode[edge[0]] = new ArrayList<>();
                prevNode[edge[1]].add(new int[]{edge[0], edge[2]});
                nextNode[edge[0]].add(new int[]{edge[1], edge[2]});
            }

            long[] shortestPath1 = dijkstra(nextNode, src1);
            long[] shortestPath2 = dijkstra(nextNode, src2);
            long[] shortestPathDest = dijkstra(prevNode, dest);

            long ans = Long.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (shortestPathDest[i] < MAX) {
                    long curAns = shortestPath1[i] + shortestPath2[i] + shortestPathDest[i];
                    ans = Math.min(ans, curAns);
                }
            }

            return ans >= MAX ? -1 : ans;
        }

        public int[][] shortenEdge(int[][] edges) {
            Map<String, Integer> shorten = new HashMap<>();
            for (int[] edge : edges) {
                String key = edge[0] + "_" + edge[1];
                if (shorten.containsKey(key)) shorten.put(key, Math.min(shorten.get(key), edge[2]));
                else shorten.put(key, edge[2]);
            }

            int[][] res = new int[shorten.size()][3];
            int i = 0;
            for (String key : shorten.keySet()) {
                int from = Integer.valueOf(key.split("_")[0]), to = Integer.valueOf(key.split("_")[1]);
                res[i++] = new int[]{from, to, shorten.get(key)};
            }

            return res;
        }

        private long[] dijkstra(List<int[]>[] nextNode, int start) {
            int n = nextNode.length;
            boolean[] visit = new boolean[n]; // 标记某节点是否被访问过
            long[] res = new long[n];     // 记录 start 点到各点的最短路径长度
            Arrays.fill(res, MAX);

            if (null != nextNode[start]) {
                for (int[] next : nextNode[start]) {
                    res[next[0]] = next[1];
                }
            }

            // 查找 n - 1 次（n 为节点个数），每次确定一个节点
            for (int i = 1; i < n; i++) {
                long min = MAX;
                int p = 0;
                // 找出一个未标记的离出发点最近的节点
                for (int j = 0; j < n; j++) {
                    if (j != start && !visit[j] && res[j] < min) {
                        min = res[j];
                        p = j;
                    }
                }
                // 标记该节点为已经访问过
                visit[p] = true;
                if (nextNode[p] == null) continue;
                for (int[] next : nextNode[p]) {
                    int j = next[0];
                    if (res[p] + next[1] < res[j]) {
                        res[j] = res[p] + next[1];  //更新最短路径
                    }
                }
            }

            res[start] = 0;
            return res;
        }
    }

    class Solution_Wrong_Thought {
        Map<Integer, Long> memo = new HashMap<>();
        int MAX = 1000000;

        public long minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
            List<int[]>[] prevNode = new List[n];
            List<int[]>[] nextNode = new List[n];
            edges = shortenEdge(edges);

            for (int[] edge : edges) {
                if (null == prevNode[edge[1]]) prevNode[edge[1]] = new ArrayList<>();
                if (null == nextNode[edge[0]]) nextNode[edge[0]] = new ArrayList<>();
                prevNode[edge[1]].add(new int[]{edge[0], edge[2]});
                nextNode[edge[0]].add(new int[]{edge[1], edge[2]});
            }

            int[] shortestPath1 = dijkstra(nextNode, src1);
            int[] shortestPath2 = dijkstra(nextNode, src2);
            long ans = dfs(dest, src1, src2, shortestPath1, shortestPath2, prevNode);
            return MAX <= ans ? -1 : ans;
        }

        public long dfs(int curDest, int src1, int src2, int[] shortestPath1, int[] shortestPath2, List<int[]>[] prevNode) {
            if (memo.containsKey(curDest)) return memo.get(curDest);
            if (curDest == src1) return shortestPath2[src1];
            if (curDest == src2) return shortestPath1[src2];
            if (null == prevNode[curDest]) return MAX;

            long curDestMinAccess = MAX;
            for (int[] prev : prevNode[curDest]) {
                long curAccess = dfs(prev[0], src1, src2, shortestPath1, shortestPath2, prevNode) + prev[1];
                curDestMinAccess = Math.min(curDestMinAccess, curAccess);
            }

            memo.put(curDest, curDestMinAccess);
            return curDestMinAccess;
        }

        public int[][] shortenEdge(int[][] edges) {
            Map<String, Integer> shorten = new HashMap<>();
            for (int[] edge : edges) {
                String key = edge[0] + "_" + edge[1];
                if (shorten.containsKey(key)) shorten.put(key, Math.min(shorten.get(key), edge[2]));
                else shorten.put(key, edge[2]);
            }

            int[][] res = new int[shorten.size()][3];
            int i = 0;
            for (String key : shorten.keySet()) {
                int from = Integer.valueOf(key.split("_")[0]), to = Integer.valueOf(key.split("_")[1]);
                res[i++] = new int[]{from, to, shorten.get(key)};
            }

            return res;
        }

        private int[] dijkstra(List<int[]>[] nextNode, int start) {
            int n = nextNode.length;
            boolean[] visit = new boolean[n]; // 标记某节点是否被访问过
            int[] res = new int[n];     // 记录 start 点到各点的最短路径长度
            Arrays.fill(res, MAX);

            if (null != nextNode[start]) {
                for (int[] next : nextNode[start]) {
                    res[next[0]] = next[1];
                }
            }

            // 查找 n - 1 次（n 为节点个数），每次确定一个节点
            for (int i = 1; i < n; i++) {
                int min = MAX;
                int p = 0;
                // 找出一个未标记的离出发点最近的节点
                for (int j = 0; j < n; j++) {
                    if (j != start && !visit[j] && res[j] < min) {
                        min = res[j];
                        p = j;
                    }
                }
                // 标记该节点为已经访问过
                visit[p] = true;
                if (nextNode[p] == null) continue;
                for (int[] next : nextNode[p]) {
                    int j = next[0];
                    if (res[p] + next[1] < res[j]) {
                        res[j] = res[p] + next[1];  //更新最短路径
                    }
                }
            }

            res[start] = 0;
            return res;
        }

//        public void dijkstraTest() {
//            int[][] edges = InputUtil.toDoubleIntegerArray("[1,2,1],[1,3,12],[2,4,3],[2,3,9],[3,5,5],[4,3,4],[4,5,13],[4,6,15],[5,6,4]");
//            List<int[]>[] nextNode = new List[7];
//            for (int[] edge : edges) {
//                if (null == nextNode[edge[0]]) nextNode[edge[0]] = new ArrayList<>();
//                nextNode[edge[0]].add(new int[]{edge[1], edge[2]});
//            }
//
//            int[] shortestPath1 = dijkstra(nextNode, 1);
//            System.out.println(Arrays.toString(shortestPath1));
//        }
    }

    public void run() {
        Solution solution = new Solution();
//        int[][] edges = InputUtil.toDoubleIntegerArray("[1,2,3]");
//        solution.dijkstraTest();
        System.out.println(solution.minimumWeight(6, InputUtil.toDoubleIntegerArray("[[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]]"), 0, 1, 5));
        System.out.println(solution.minimumWeight(6, InputUtil.toDoubleIntegerArray("[[0,1,1],[2,1,1]]"), 0, 1, 2));
        System.out.println(solution.minimumWeight(8, InputUtil.toDoubleIntegerArray("[[4,7,24],[1,3,30],[4,0,31],[1,2,31],[1,5,18],[1,6,19],[4,6,25],[5,6,32],[0,6,50]]"), 4, 1, 6));
    }

    public static void main(String[] args) throws Exception {
        LC6032 an = new LC6032();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
